package 平衡二叉树;

import javax.swing.tree.TreeNode;

public class Solution {

    /*
     * 时间复杂度O（N）
     * */
    public boolean isBalanced2(TreeNode root) {
        if (getHeight2(root) == -1) {
            return false;
        }
        return true;
    }

    /*
     * 时间复杂度O（N^2）
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        if (Math.abs((leftH - rightH)) >= 2) {   // 这里不能用 <=1 因为根节点的左子树和右子树符合二叉平衡树时，他的根节点的左子树的左右子树和右子树的左右子树不一定符合
            return false;
        }
        boolean retleft = isBalanced(root.left);
        boolean retright = isBalanced(root.right);
        return retleft && retright;

        /*        return Math.abs(leftH - rightH) < 2 && isBalanced(root.left) && isBalanced(root.right);*/

    }

    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    public int getHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (Math.abs(leftHeight-rightHeight)>=2 || leftHeight<0 || rightHeight<0){
            return -1;
        }else {
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }
}
